package main

import "go-study/algorithm/common"

// 如何翻转栈的所有元素
// 引申：如何给栈排序

func main() {
	stack := common.CreateStack([]int{5, 2, 3, 4, 1})
	common.PrintStack(stack)
	reverseStack(stack)
	common.PrintStack(stack)
}

func reverseStack(s *common.LinkedStack) {
	if s.IsEmpty() {
		return
	}
	//moveBottomToTop(s)
	moveSmallestToTop(s)
	top := s.Pop()
	reverseStack(s)
	s.Push(top)
}

func moveBottomToTop(s *common.LinkedStack) {
	if s.IsEmpty() {
		return
	}
	top1 := s.Pop()
	if !s.IsEmpty() {
		moveBottomToTop(s)
		top2 := s.Pop()
		s.Push(top1)
		s.Push(top2)
	} else {
		s.Push(top1)
	}
}

func moveSmallestToTop(s *common.LinkedStack) {
	if s.IsEmpty() {
		return
	}

	top1 := s.Pop()
	if s.IsEmpty() {
		s.Push(top1)
		return
	}
	moveSmallestToTop(s)
	top2 := s.Pop()
	if top1 < top2 {
		s.Push(top2)
		s.Push(top1)
	} else {
		s.Push(top1)
		s.Push(top2)
	}
}
